package com.wp.algorithm.a1_dynamic_programing.code;

import java.util.Vector;

/**
 * @author wangpeng
 * @description 斐波那切数列
 * @date 2021/11/11 11:05
 */
public class Test1Fib {
    public static void main(String[] args) {
        int param = 30;
        if(param<0){
            System.out.println("");
        }

        Vector<Integer> vector = new Vector<>(param+1);
        vectorInnit(vector);


        System.out.println(m2(param+1,vector));
        System.out.println(m(param+1));
        System.out.println(m3(param));
    }




    private static void vectorInnit (Vector<Integer> vector) {
        for (int i = 0; i < vector.capacity(); i++) {
            if(i<2){
                vector.add(i,i);
            }else {
                vector.add(i,null);
            }
        }

    }


    private static Integer m3 (int n) {
        if(n==1||n==2){
            return 1;
        }
        int prev = 1;
        int curr = 1;
        for (int i = 3; i <= n; i++) {
            int sum = prev+curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
    /**
     *
     * @param n
     * @return
     */
    private static Integer m2 (int n,Vector<Integer> vector) {
        Integer value = vector.get(n-1);
        if(value!=null){
            return value;
        }
        Integer value_n_1 = vector.get(n-2);

        Integer value_n_2 = vector.get(n-3);
        if(value_n_1==null){
            value_n_1 = m2(n-1,vector);
        }
        if(value_n_2==null){
            value_n_2 = m2(n-2,vector);
        }
        return value_n_1+value_n_2;
    }

    /**
     * 暴力递归
     * @param n
     * @return
     */
    private static Integer m(int n) {
        if(n==1||n==2){
            return n-1;
        }
        return m(n-1)+m(n-2);
    }
}
